#include<iostream>

#define DEGREE 2    // Deafault Degree

using KEY_VALUE = int;
using UINT = unsigned int;

/*
    B树的性质：
    1. 每个节点至多有 degree 颗子树。
    2. 每个非根结点至少有 min = degree/2 颗子树。
    3. 非叶子结点的关键字之间必定有非空子树（keys = children -1）
    4. 叶子结点的所有子树为空，且都为同一层
*/

struct BTreeNode
{
    // 无父指针的B树结点
    BTreeNode(UINT degree)
    : _size(0), _leaf(true)
    {
        _keys = new KEY_VALUE[degree-1];
        _children = new BTreeNode*[degree];
    }

    void destroy()
    {
        if(_keys != nullptr)
            delete _keys;
        if(_children != nullptr)
            delete _children;
        if(_parent != nullptr)
            delete _parent;
        _keys = nullptr;
        _children = nullptr;
        _parent = nullptr;
    }
    /* data */
    KEY_VALUE*  _keys;          // key值序列
    BTreeNode** _children;      // 子树序列   
    BTreeNode* _parent;  
    UINT   _size;   // keys 关键字数, keys = children - 1
    bool   _leaf;   // isleaf
};

class BTree
{
public:
    // construct
    BTree()
    : _degree(DEGREE), _min(DEGREE/2)
    {
        create();
    }
    BTree(int degree)
    : _degree(degree), _min(degree/2)
    {
        create();
    }
    // 拷贝构造
    BTree(const BTree& tree)
    {

    }
    ~BTree();

    // func
    // friend bool searchNode(const KEY_VALUE key, BTreeNode* node, BTreeNode* ptr);
    // 查找
    BTreeNode* search(const KEY_VALUE key)
    {
        if(empty())
            return nullptr;
        return searchNode(key, _root);
    }
    // 增添
    void add(const KEY_VALUE nkey)
    {
        // 增加元素只会在叶子节点完成
        // 如果是根节点，那么走根分裂，如果是其他节点，走分支分裂
        BTreeNode* ptr = _root;
        KEY_VALUE key = nkey;

        if(ptr->_leaf)
            splitroot(key);
        else 
            insert(ptr, key);
    }
    // 删除
    void del(const KEY_VALUE key)
    {
        if(empty())
            return ;
        BTreeNode* target = search(key);
        if(nullptr == target)
            return;
        delnode(target, key, 0);    
    }
    // 获得树
    BTreeNode* getTree() const
    {
        return _root;
    }

private:
    // 树的判空
    bool empty() const 
    {
        return 0==_root->_size;
    }
    // 建树
    void create()
    {
        _root = new BTreeNode(_degree);
    }
    // 查找的递归
    BTreeNode* searchNode(KEY_VALUE key,  BTreeNode* node) 
    {
        int num = node->_size;
        // 减治法递归
        for(int i = 0; i < node->_size; i++)
        {
            if(node->_keys[i] == key)
                return node;
            else if(node->_keys[i] > key)
            {
                // 如果查找到叶子节点，查找失败
                if(node->_leaf)
                    return nullptr;
                searchNode(key, node->_children[i]);   
            }
        } 
        // 递归完成仍未找到
        return nullptr;
    }

    // 对分支节点进行分裂
    void splitchild(BTreeNode* node, int index)
    {
        // 分裂后的靠右节点
        BTreeNode* rchild = new BTreeNode(_degree);
        // 要分裂的靠左节点 但暂时左节点先占用整个子节点
        BTreeNode* lchild = node->_children[index]; 
        rchild->_leaf = lchild->_leaf;
        rchild->_size = _min-1;
        rchild->_parent = node;

        // 把右半边的键值复制给新节点
        for(int i = 0; i <= _min-1; i++)
            rchild->_keys[i] = lchild->_keys[i+_min];
        
        // 如果分裂的不是叶子节点， 那么把子树也一起复制过去
        if(!lchild->_leaf)
            for(int i = 0; i <= _min; i++)
                rchild->_children[i] = lchild->_children[i+_min];

        // b树是从下向上生长的
        // 把父节点的键值挪动
        for(int i = node->_size-1; i >= index; i--)
            node->_keys[i+1] = node->_keys[i];
        // 把对应键值间的指针也对应挪动
        for(int i = node->_size; i >= index; i--)
            node->_children[i+1] = node->_children[i];
        //把靠右节点挂载到根节点
        node->_children[index+1] = rchild;
         // 把被分裂的key值生长给根节点
        node->_keys[index] = lchild->_keys[_min];
        
        // 调整左节点分裂后关键字的数量
        lchild->_size = _min-1;
        node->_size++;
    }
    // 对根节点进行插入后分裂
    void splitroot(KEY_VALUE key)
    {
        BTreeNode* root = _root;
        // 如果根节点需要分裂 那么先生成一个新的空节点作为新的根节点
        // 原结点试为其子节点，然后进行分裂
        if(root->_size == _degree-1)
        {
            BTreeNode* nroot = new BTreeNode(_degree);
            nroot->_leaf = false;
            nroot->_children[0] = root;
            root->_parent = nroot;
            splitchild(root, 0);
            _root = nroot;
        }

        insert(_root, key);
    }
    // 对有空余的节点进行插入
    void insert(BTreeNode* node, KEY_VALUE key)
    {
        int num = node->_size;
        if(node->_leaf)
        {
            while (num > 0 && key < node->_keys[num-1])
            {
                // 比当前key小，向左插
                node->_keys[num] = node->_keys[num-1];
                num--;
            } 
            node->_keys[num] = key;
            node->_size++;

        }
        else 
        {
            while(num > 0 && key < node->_keys[num-1])
                num--;

            if(node->_children[num]->_size == _degree-1)
            {
                splitchild(node, num);
                if(key > node->_keys[num])
                    num++;
            }
            insert(node->_children[num], key);
        }
    }
    // 判断前继后继是否能借位
    UINT isEnough(BTreeNode* node, int index)
    {
        if(index == 0)  // 是头部
        {
            if(node->_children[index+1]->_size > _min-1)
                return 1;
        }
        else if(index == _min-1)  // 是尾部
        {
            if(node->_children[index-1]->_size > _min-1)
                return 0;
        }
        else // 在中间
        {
            if(node->_children[index-1]->_size > _min-1)
                return 0;
            if(node->_children[index+1]->_size > _min-1)
                return 1;
        }
        return 2;
    }
    // 调整B树使其符合性质 index --- node 在 parent 中的位置
    void balance(BTreeNode* node, BTreeNode* parent, int index)
    {
        enum Flag{PEER = 0, NEXT, MERGE};
        int flag;
        // 删除关键字前，先判断是否还满足B树性质，否则则调整
        flag = isEnough(parent, index);
        if(flag == PEER)
        {
            // 前置有多余 前置最近关键字给父亲
            // 父亲的对应关键字下放到儿子填空位
            BTreeNode* bro = parent->_children[index-1];
            int nkey = parent->_keys[index-1];
      
            parent->_keys[index-1] = bro->_keys[bro->_size];
            bro->_size--;
            // 将关键词替换
            parent->_children[index]->_keys[0] = nkey;
        }
        else if (flag == NEXT)
        {
            // 后置有多余 后置最近关键字给父亲
            // 父亲的对应关键字下放到儿子填空位
            BTreeNode* bro = parent->_children[index+1];
            int nkey = parent->_keys[index+1];
            // 挪位
            parent->_keys[index+1] = bro->_keys[0];
            for(int i = 0; i < bro->_size-1; i++)
                bro->_keys[i] = bro->_keys[i+1];
            bro->_size--;
            // 将关键词替换
            BTreeNode* child = parent->_children[index];
            child->_keys[child->_size] = nkey;
      
        }
        else if (flag == MERGE)
        {
            // 父有多余 前置关键字下沉，与前后子树一起合并
            int nkey = parent->_keys[index-1];
            // 合并得到新节点
            BTreeNode* nnode = merge(parent->_children[index], parent->_children[index-1], nkey);
            // 挪动后挂载新节点
            for(int i = index; i < parent->_size-1; i++)
                parent->_keys[i] = parent->_keys[i+1];
            for(int i = index; i < parent->_size; i++)
                parent->_children[i] = parent->_children[i+1];
            parent->_size--;
            parent->_children[index] = nnode;
            // 如果借位后父亲结点不满足性质，对父亲进行平衡
            if(parent->_size < _min-1)
            {
                int right = parent->_keys[parent->_size-1];
                int i;
                // 找到结点在父亲中的位置
                for(i = 0; i < parent->_parent->_size-1; i++)
                {
                    if(parent->_parent->_keys[i] > right)
                        break;
                }
                balance(parent, parent->_parent, i);
            }
        }            
      
    }
    BTreeNode* merge(BTreeNode* node, BTreeNode* peer, KEY_VALUE key)
    {
        BTreeNode* nnode = new BTreeNode(_degree);
        nnode->_size = node->_size + peer->_size + 1;
        // 把左右复制过来
        int index = 0;
        while(index != nnode->_size)
        {
            for(; index < node->_size; index++)
            {
                nnode->_keys[index] = node->_keys[index];
                nnode->_children[index] = node->_children[index];
            }
            nnode->_children[index] = node->_children[index];
            nnode->_keys[index] = key;
            index ++;
            for(int i = 0; i < peer->_size; i++)
            {
                nnode->_keys[index] = peer->_keys[i];
                nnode->_children[index] = peer->_children[i];
                index ++;
            }
            nnode->_children[index] = peer->_children[index];
        }
        nnode->_leaf = node->_leaf;
        nnode->_parent = node->_parent;
        return nnode;
    }
    void delnode(BTreeNode* node, KEY_VALUE key, int index)
    {
        int it = 0;
        
        while(node->_keys[it]< key)
            it ++;

        if(node->_keys[it] == key)
        {
            // 挪动
            for(int i = it; i < node->_size-1; i ++)
                node->_keys[i] = node->_keys[i+1];
            node->_size--;

            // 删除后若不满足B树性质，平衡
            if(node->_size < _min-1)
            {
                BTreeNode* parent = node->_parent;
                int i;
                for(i = 0; i < parent->_size-1; i++)
                {
                    if(parent->_keys[i] > key)
                        break;
                }
                balance(node, parent, index);
            }    
        }
        else
        {
            node = node->_children[it];  // 此层未找到，根据序号跳到对应子节点继续寻找
            delnode(node, key, it);
        }
    }

private:
    /* data */
    BTreeNode* _root;
    UINT _degree;
    UINT _min;
};
